1. Field of the Invention
The present invention relates to computations represented by dependency graphs and, more particularly, to a method of utilizing product proxies with a dependency graph to avoid unnecessary computations after the graph has been changed.
2. Description of the Related Art
A dependency graph is a hierarchical set of nodes that describe a set of input data and computations which, when evaluated, produce output data that represents the state of the graph. One example of a dependency graph is a scene graph in computer graphics which, when evaluated, produces output data that represents the state of a 3D scene. A scene graph encodes, for example, the shape, location, and motion of the objects that appear in the 3D scene, or how these objects are illuminated by one or more virtual light sources.
FIG. 1 shows a diagram that illustrates an example of a prior-art dependency graph 100. As shown in FIG. 1, dependency graph 100 includes a number of hierarchically-ordered nodes 110. The nodes 110, which have a dependency relationship, include attribute nodes 110A and operator nodes 110P. In addition, a node 110 can have one or more input connectors 110N and one or more output connectors 110T.
Attribute nodes 110A contain the input data for the computations described by the dependency graph. An attribute node 110A stores and outputs a value that is typically input by a user. In a dependency graph that represents a scene in computer graphics, the value held by an attribute node 110A can represent, for example, the shape of a surface or the color of a light source.
An operator node 110P, in turn, 5 represents a computation that, when evaluated, transforms input data, such as the data received from an attribute node 110A or another operator node 110P, into output data known as products. An operator node 110P receives its input data via the input connectors 110N, and it outputs its products via the output connectors 110T. In addition, an operator node 110P has a separate output connector 110T for each of its products. In some cases, attribute and operator nodes 110A and 110P may be combined, i.e., a single node 110 may represent a computation and at the same time store some of the input data required by the computation.
In the FIG. 1 example, an output connector 110T1 of an attribute node 110A1 and an output connector 110T2 of an attribute node 110A2 are connected to input connectors 110N1 and 110N2, respectively, of an operator node 110P1. When evaluated, attribute nodes 110A1 and 110A2 output first and second products D1 and D2 on output connectors 110T1 and 110T2, respectively, while operator node 110P1 outputs third and fourth products D3 and D4 on output connectors 110T3 and 110T4, respectively, computing the products from data received via input connectors 110N1 and 110N2.
In addition, an output connector 110T5 of an attribute node 110A3 and the output connector 110T4 of operator node 110P1 are connected to the input connectors 110N3 and 110N4, respectively, of an operator node 110P2. When evaluated, attribute node 110A3 outputs a fifth product DS on output connector 110T5, while operator node 110P2 outputs a sixth product D6 on output connector 110T6, computing the product from data received via input connectors 110N3 and 110N4.
Further, output connector 110T3 of operator node 110P1 and output connector 110T6 of operator node 110P2 are connected to the input connectors 110N6 and 110N7, respectively, of an operator node 110P3. When evaluated, operator node 110P3 outputs a seventh product D7 on output connector 110T7, computing the product from data received via input connectors 110N6 and 110N7.
The computation performed by an operator node 110P can have any level of complexity, ranging from a trivial computation to an extremely complex computation. One example of a trivial computation is simply adding two numbers together to produce a product that is the sum of those numbers.
On the other hand, one example of a complex computation is a physical simulation that determines the motion paths of a number of colliding rigid bodies. In this example, the product that results from the computation might consist of the trajectories of the rigid bodies.
A dependency graph is constructed by creating and connecting attribute and operator nodes 110A and 110P to build up a set of input data and computations that describe the state of the graph. The computations, however, are performed only when the dependency graph is evaluated.
Once constructed, a dependency graph can be saved in a file for later evaluation. When a user wishes to obtain one or more of the products represented by the dependency graph, the dependency graph must be evaluated. (In this context, “user” can refer to either a person or to application software that queries the dependency graph.) Evaluation determines the desired products by traversing the dependency graph in a predetermined order, starting at the output connectors 110T that correspond to those products.
Evaluating a dependency graph does not require that all of the products in the graph be computed. Only the desired products, and the products that contribute to the desired products, need to be computed. The parts of the dependency graph that are unrelated to the products the user wants to obtain are not traversed at all. In the FIG. 1 example, to determine the seventh product 07 of operator node 110P3, the values of the third product 03 and the sixth product 06 input to operator node 110P3 must be determined.
To determine the value of product 06 output by operator node 110P2, the values of the fourth product 04 and the fifth product 05 must be determined. To determine the value of products 03 and 04 output by operator node 110P1, the products 01 and 02 from attribute nodes 110A1 and 110A2, respectively, must be determined. In this way, evaluation traverses the scene graph, gathering input data from the attribute nodes 110A, and combining them to obtain the requested product.
It is a common practice to make changes to a dependency graph. In a computer graphics context, users commonly make changes to a 3D scene by making changes to the scene graph. For example, the values held by the attribute nodes 110A can be changed, nodes can be added or removed, and computations and connections between nodes can be changed.
When a dependency graph is changed in this way, the changes may cause one or more products from a previous evaluation of the dependency graph to be different from what one would get by evaluating the scene graph in its current state. In order to obtain new products that correspond to the changed dependency graph, the new dependency graph must be re-evaluated.
One approach to obtaining new products is to re-evaluate the dependency graph, starting at the output connectors 110T that correspond to products that the user has previously obtained. However, depending on the complexity of the computations performed by the operator nodes, re-evaluating a dependency graph to generate a product can be extremely time-consuming. Operations such as physical simulations can take many hours to complete.
Another approach to obtaining new products, which minimizes the time required to re-evaluate the dependency graph, is to save the products of the first evaluation and, after changing the dependency graph, determine which products are no longer valid as a result of the changes. After this, the invalid products are discarded. Thus, rather than discarding and re-computing all of the products every time the dependency graph is changed, only the products that may have changed as a result of the dependency graph changes are re-computed.
Determining which products become invalid when the dependency graph changes is typically done using a technique known as invalidation. With invalidation, when an attribute, an operator, or a connection is added or removed, or the value of an attribute is modified, the dependency graph is traversed, starting at the point where the change occurred, and following the connections from the output connectors 110T to the input connectors 110N, in the opposite direction as during evaluation.
When, during the traversal, an output connector 110T is encountered, for which a product has been saved, the product is marked as invalid. A product is invalid if it is not the same as what one would get by re-evaluating the scene graph in its current state. The remaining products, on the other hand, remain valid.
After invalidation, the dependency graph can be re-evaluated as before except that when a product from the first evaluation remains valid, it is re-used. As a result, as the dependency graph is traversed, only the products affected by the change are re-calculated, thereby significantly reducing the time required to re-evaluate the dependency graph.
One limitation of invalidation is that it typically does not work across sessions. When a session is terminated and a new session is started, all products are considered invalid at the beginning of the new session. Another limitation of invalidation is that if the dependency graph is changed, and then subsequently restored to its previous state, then the products associated with the restored part of the dependency graph are considered invalid.
A complex dependency graph is often broken up into multiple pieces that can be loaded and unloaded independently, so that multiple users can simultaneously work on different parts of the dependency graph. With invalidation, when a valid part of a dependency graph is unloaded and then subsequently reloaded, products that correspond to the reloaded part of the dependency graph can no longer be considered valid.
One problem which commonly arises when working with dependency graphs is that it is difficult to determine if products obtained by evaluating a dependency graph represent the current state of the dependency graph. In the context of computer graphics, where dependency graphs are employed to represent 3D scenes, this problem is particularly evident in larger animation studios where multiple groups of people are responsible for changing various parts of the dependency graph, and other groups are responsible for evaluating the dependency graph. Thus, there is a need for a method of utilizing a dependency graph that addresses these issues.